//我们有两个长度相等且不为空的整型数组 A 和 B 。 
//
// 我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。 
//
// 在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.lengt
//h - 1]）。 
//
// 给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。 
//
// 
//示例:
//输入: A = [1,3,5,4], B = [1,2,3,7]
//输出: 1
//解释: 
//交换 A[3] 和 B[3] 后，两个数组如下:
//A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
//两个数组均为严格递增的。 
//
// 注意: 
//
// 
// A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。 
// A[i], B[i] 均为 [0, 2000]区间内的整数。 
// 
// Related Topics 数组 动态规划 
// 👍 193 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;
public class MinimumSwapsToMakeSequencesIncreasing {
    public static void main(String[] args) {
        Solution solution = new MinimumSwapsToMakeSequencesIncreasing().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minSwap(int[] A, int[] B) {
        int dp0 = 0;
        int dp1 = 1;
        int newDp0 = 0;
        int newDp1 = 0;
        for (int i = 1; i < A.length; i++) {
            if (A[i-1]<A[i] && B[i-1]<B[i]){
                //有序且无交叉，可换可不换
                if (A[i-1]<B[i] && B[i-1]<A[i]){
                    newDp0 = Math.min(dp0,dp1);
                    newDp1 = Math.min(dp0,dp1)+1;
                }
                // 有序且有交叉，若换则前一个也要换，不换则前一个也不换
                else {
                    newDp0 = dp0;
                    newDp1 = dp1+1;
                }
            }else {
                // 无序，则换，前一个不换，或者不换，前一个换
                newDp0 = dp1;
                newDp1 = dp0+1;
            }
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return Math.min(dp0,dp1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}